// add test code and compile,
// or simply copy/paste this file in the interpreter and play around with it

//package fst.simplified

object Parsing {

type Input = String

trait Result[+T] 

case class Success[+T](result: T, rest: Input) extends Result[T]
case class Failure(errMsg: String, rest: Input) extends Result[Nothing]

def Parser[T](f: Input => Result[T]): Parser[T] 
    = new Parser[T]{ def apply(in: Input) = f(in) }
    
abstract class Parser[+T] extends (Input => Result[T]) { 
  private var name: String = ""
  def debug(n: String) = {name=n; println(n); this}
  override def toString() = name
  
  def ~ [U](p: => Parser[U]): Parser[Pair[T, U]]
    = Parser { in: Input => 
      this(in) match {
        case Success(x, rest) => 
          p(rest) match {
            case Success(y, rest2) => Success((x, y), rest2)
            case Failure(e, r) => Failure(e, r)
          }
        case Failure(e, r) => Failure(e, r)
      }
    } debug(this+" ~ ...")
    
  def ~> [U](p: => Parser[U]): Parser[U] = this ~ p ^^ {case (x, y) => y}
  def <~ [U](p: => Parser[U]): Parser[T] = this ~ p ^^ {case (x, y) => x}
      
  def | [U >: T](p: => Parser[U]): Parser[U]
    = Parser { in: Input => 
      this(in) match {
        case s@Success(_, _) => s
        case _ => p(in)
      }
    } debug(this+" | ...")  
    
  def ^^ [U](f: T => U): Parser[U]
    = Parser { in: Input => 
        this(in) match {
          case Success(x, r) => Success(f(x), r)
          case Failure(e, r) => Failure(e, r)
        }
      } debug(this+ "lifted")     
}  
  
implicit def accept(e: Char): Parser[Char] 
  = Parser { in: String => 
    if(!in.isEmpty && in(0) == e) Success(e, in.substring(1))
    else Failure("expected "+e, in)
  } debug("accept "+e)

def rep1[T](p: Parser[T]): Parser[List[T]] 
  = 
  ( p ~ rep1(p) ^^ {case (x, xs) => x :: xs} 
  | p ^^ {x => List(x)}
  )
  
def rep[T](p: => Parser[T]): Parser[List[T]] 
  = rep1(p) | success(List())  
    
def chainl1[T](p: => Parser[T], q: => Parser[(T, T) => T]): Parser[T] 
  = p ~ rep(q ~ p) ^^ {
      case (x, xs) => xs.foldLeft(x){(_, _) match {case (a, (f, b)) => f(a, b)}}
    }

def success[T](v: T): Parser[T] = Parser{in => Success(v, in)}

def acceptIf(p: Char => Boolean): Parser[Char] 
  = Parser { in: String => 
    if(!in.isEmpty && p(in(0))) Success(in(0), in.substring(1))
    else Failure("acceptIf failed", in)
  }
  
def opt[T](p: => Parser[T]): Parser[Option[T]] 
  = ( p ^^ {x: T => Some(x)} 
    | success(None)
    )
        
def rep1[T](first: Parser[T], p: Parser[T]): Parser[List[T]] 
  = 
  ( first ~ rep1(p) ^^ {case (x, xs) => x :: xs} 
  | first ^^ {x => List(x)}
  )
}

class Term
case class Var(name: String) extends Term
case class Abs(name: String, body: Term) extends Term
case class App(fun: Term, arg: Term) extends Term

import Parsing._

object Grammar {
def letter = acceptIf(_.isLetter)
def digit = acceptIf(_.isDigit)
def ws = rep1(accept(' '))
def wss[T](p: Parser[T]): Parser[T] = opt(ws) ~> p <~ opt(ws)
def ident = (rep1(letter, letter | digit) ^^ {_.mkString("")}).debug("ident")

def term_ : Parser[Term] = 
   ( ('\\' ~> wss(ident)).debug("a") ~ ('.' ~> wss(term)).debug("b") ^^ {case (i, b) => Abs(i, b)}
   | ident ^^ {n => Var(n)}
   )

def term = chainl1(term_, ws ^^ {x => App(_: Term, _: Term)})
}

import Grammar._

//def main(args: Array[String]) = println(term(args(0)))
